/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/maximum-distance-in-arrays
   @Language: C++
   @Datetime: 20-01-19 15:51
   */

// Method 1, Time O(mlogm) 203ms
class Solution {
public:
	/**
	 * @param arrs: an array of arrays
	 * @return: return the max distance among arrays
	 */
	int maxDiff(vector<vector<int>> &arrs) {
		// write your code here
		map<int, unordered_set<int> > nums;
		for(int i=0; i<arrs.size(); ++i){
			nums[arrs[i][0]].insert(i);
			nums[arrs[i].back()].insert(i);
		}
		queue<pair<decltype(nums.begin()), decltype(nums.rbegin())> > q;
		auto isDiff = [](unordered_set<int> &a, unordered_set<int> &b)->bool{
			for(const auto &i:a)
				if (!b.count(i)) return true;
			return false;
		};
		int diff=0;
		for(q.push({nums.begin(), nums.rbegin()}); q.size(); q.pop()){
			auto &i=q.front().first;
			auto &j=q.front().second;
			if (!isDiff(i->second, j->second)){
				auto ii=i++;
				if (i!=nums.end()) q.push({i, j});
				if (++j!=nums.rend()) q.push({ii, j});
			}
			else diff = max(diff, abs(i->first-j->first));
		}
		return diff;
	}
};


// Method 2, Time O(m) 101ms
class Solution {
public:
	/**
	 * @param arrs: an array of arrays
	 * @return: return the max distance among arrays
	 */
	int maxDiff(vector<vector<int>> &arrs) {
		// write your code here
		int diff=0, n=arrs[0][0], m=arrs[0].back();
		for(int i=1; i<arrs.size(); ++i){
			diff=max(diff, max(abs(m-arrs[i][0]), abs(arrs[i].back()-n)));
			n=min(n, arrs[i][0]);
			m=max(m, arrs[i].back());
		}
		return diff;
	}
};
